package leetcode.leetcode206;

/**
 * @author czt
 * @version 1.0
 * @since 2024/12/16
 */
public class Leetcode206 {

    /**
     * 反转链表1-创建一个新链表，遍历旧的链表，并将遍历到的节点插入到新链表的头部
     * @param head 链表头部
     * @return 链表尾部
     */
    public ListNode reverseList1(ListNode head) {
        // 新的链表，头部指针
        ListNode n1 = null;

        // 遍历之前的链表
        ListNode p = head;
        while (p != null) {
            // 每次插入的元素的next指向新链表的头部，并更新n1
            n1 = new ListNode(p.val, n1);
            p = p.next;
        }
        return n1;
    }

    /**
     * 反转链表2-创建一个新链表，遍历旧的链表，将旧链表的头部节点删除并插入到新链表的头部
     * @param head 链表头部
     * @return 链表尾部
     */
    public ListNode reverseList2(ListNode head) {
        List list1 = new List(head);
        List list2 = new List(null);
        while (true) {
            ListNode first = list1.removeFirst();
            if (first == null) {
                break;
            }
            list2.addFirst(first);
        }

        return list2.head;
    }

    static class List {
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }

        /**
         * 向头部添加节点
         * @param first 第一个节点
         */
        public void addFirst(ListNode first) {
            // 使第一个节点添加到头部
            first.next = head;
            // 更新头节点
            head = first;
        }

        /**
         * 删除并返回第一个节点
         * @return 节点值
         */
        public ListNode removeFirst() {
            ListNode first = head;
            if (first != null) {
                // 将头节点指向之前头节点的下一个节点
                head = first.next;
            }
            return first;
        }
    }

    /**
     * 反转链表3-递归
     * @param head 链表头部
     * @return 链表尾部
     */
    public ListNode reverseList3(ListNode head) {
        if (head == null || head.next == null) {
            // 找到最后节点
            return head;
        }
        ListNode last = reverseList3(head.next);

        head.next.next = head;
        head.next = null;

        return last;
    }

    public static void main(String[] args) {
        ListNode o5 = new ListNode(5, null);
        ListNode o4 = new ListNode(4, o5);
        ListNode o3 = new ListNode(3, o4);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);

        System.out.println(o1);

        ListNode n1 = new Leetcode206().reverseList1(o1);

        System.out.println(n1);
    }

}
